package newcoder;

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Stack;

public class NC115 {

    public static int[] solve (int[] a) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((x,y)->y-x);
        for(int n:a){
            pq.add(n);
        }
        int[] res = new int[a.length];
        int r=0;
        for(int i =0;i<a.length;i++){
            if(pq.isEmpty()) break;
            int max = pq.poll();
            while(!stack.isEmpty()&&stack.peek()>=max){
                res[r++] = stack.pop();
            }
            while(a[i]!=max){
                stack.add(a[i]);
                pq.remove(a[i]);
                i++;

            }
            res[r++]=max;
        }
        while(!stack.isEmpty()) res[r++] = stack.pop();
        return res;
    }

    public static void main(String[] args) {

        System.out.println(solve(new int[]{5,8,9,6,7,1,3,2,4}));
    }
}
